package com.lyt.springboot.util.algorithm;

public class S5 {
    //快速排序again
    public void quickSort(int[] arr,int left,int right) {
        if(left>=right) {
            return;
        }
        //选定一个基准key 默认最左边
        int key = arr[left];
        //定义两个左右指针
        int i= left;
        int j = right;

        //i<j
        while(i<j) {
            //先移动右指针
            while (i<j && arr[j]>=key) {
                j--;
            }
            //再移动左指针
            while (i<j && arr[i]<= key) {
                i++;
            }
            //左右指针交换值
            swap(arr,i,j);
        }
        //循环结束后交换值left，i  此时ij
        swap(arr,left,i);
        //递归
        quickSort(arr,left,i-1);
        quickSort(arr,j+1,right);
    }
    public int[] swap(int[]arr,int i,int j) {
        int temp = 0;
        if(i<=arr.length && j<=arr.length) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        return arr;
    }
}
